#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <memory>
#include <utility>
#include <stdexcept>
#include <stack>
#include "Iterator.h"

// 根节点至少有两个孩子 
// 每个非根节点至少有M/2（上取整）个孩子，至多有M个孩子。
// 每个叶子节点 至少有 M/2-1（上取整）个关键字，至多有 M-1 个关键字。并以升序排列
// key[i] 和 key[i+1] 之间的孩子节点的值介于 key[i] 和 key[i+1] 之间
// 所有的叶子节点都在同一层

// B树节点定义
template <typename T, int Order>
struct b_tree_node {
    bool is_leaf;                  // 是否为叶子节点
    int key_count;                 // 当前关键字数量
    T keys[Order - 1];             // 关键字数组
    b_tree_node* children[Order];  // 子节点数组

    // 构造函数
    b_tree_node() : is_leaf(true), key_count(0) {
        for (int i = 0; i < Order; ++i) {
            children[i] = nullptr;
        }
    }

    // 查找关键字位置
    int find_key(const T& key) const {
        int idx = 0;
        while (idx < key_count && keys[idx] < key) {
            idx++;
        }
        return idx;
    }
};

// B树迭代器
template <typename T, int Order>
class b_tree_iterator 
    : public my_stl::iterator<my_stl::bidirectional_iterator_tag, T> {
public:
    using value_type = T;
    using reference = T&;
    using pointer = T*;
    using difference_type = ptrdiff_t;
    using iterator_category = my_stl::bidirectional_iterator_tag;
    using self = b_tree_iterator<T, Order>;

private:
    // 用于保存遍历路径的结构
    struct stack_frame {
        b_tree_node<T, Order>* node;
        int index;
        stack_frame(b_tree_node<T, Order>* n, int i) : node(n), index(i) {}
    };

    std::stack<stack_frame> path_stack;  // 遍历路径栈
    b_tree_node<T, Order>* current_node; // 当前节点
    int current_index;                   // 当前关键字索引
    bool is_end;                         // 是否为结束迭代器

    // 初始化栈，找到最左节点
    void initialize_stack(b_tree_node<T, Order>* root) {
        if (!root) return;
        
        b_tree_node<T, Order>* node = root;
        while (node) {
            path_stack.push(stack_frame(node, 0));
            if (node->is_leaf) break;
            node = node->children[0];
        }
        
        if (!path_stack.empty()) {
            current_node = path_stack.top().node;
            current_index = 0;
            is_end = false;
        } else {
            is_end = true;
        }
    }

public:
    // 构造函数
    b_tree_iterator() : current_node(nullptr), current_index(-1), is_end(true) {}
    b_tree_iterator(b_tree_node<T, Order>* root) : current_node(nullptr), current_index(-1), is_end(true) {
        if (root) {
            initialize_stack(root);
        }
    }

    // 解引用操作符
    reference operator*() const {
        if (is_end || current_index >= current_node->key_count) {
            throw std::out_of_range("B树迭代器解引用");
        }
        return current_node->keys[current_index];
    }

    // 成员访问操作符
    pointer operator->() const {
        return &(operator*());
    }

    // 前置++
    self& operator++() {
        if (is_end) return *this;

        // 如果当前节点还有下一个关键字
        if (current_index + 1 < current_node->key_count) {
            current_index++;
            return *this;
        }

        // 否则需要移动到下一个节点
        if (current_node->is_leaf) {
            // 从栈中弹出当前节点
            path_stack.pop();
            
            // 回溯查找可以向右移动的节点
            while (!path_stack.empty()) {
                stack_frame& parent = path_stack.top();
                b_tree_node<T, Order>* parent_node = parent.node;
                int parent_idx = parent.index;

                // 如果父节点有下一个关键字
                if (parent_idx + 1 < parent_node->key_count) {
                    parent.index++;
                    current_node = parent_node;
                    current_index = parent_idx + 1;
                    return *this;
                } else {
                    // 进入父节点的下一个子节点
                    if (!parent_node->is_leaf) {
                        b_tree_node<T, Order>* child = parent_node->children[parent_idx + 1];
                        // 找到这个子树的最左节点
                        while (!child->is_leaf) {
                            path_stack.push(stack_frame(child, 0));
                            child = child->children[0];
                        }
                        path_stack.push(stack_frame(child, 0));
                        current_node = child;
                        current_index = 0;
                        return *this;
                    } else {
                        // 父节点是叶子节点，继续回溯
                        path_stack.pop();
                    }
                }
            }

            is_end = true;
            current_node = nullptr;
            current_index = -1;
        } else {
            // 非叶子节点，进入当前关键字右侧的子节点并找到最左关键字
            b_tree_node<T, Order>* child = current_node->children[current_index + 1];
            while (!child->is_leaf) {
                path_stack.push(stack_frame(child, 0));
                child = child->children[0];
            }
            path_stack.push(stack_frame(child, 0));
            current_node = child;
            current_index = 0;
        }

        return *this;
    }

    // 后置++
    self operator++(int) {
        self temp = *this;
        ++(*this);
        return temp;
    }

    // 前置--
    self& operator--() {
        throw std::runtime_error("B树迭代器：--操作未实现");
        return *this;
    }

    // 后置--
    self operator--(int) {
        self temp = *this;
        --(*this);
        return temp;
    }

    // 相等比较
    bool operator==(const self& other) const {
        if (is_end && other.is_end) return true;
        if (is_end || other.is_end) return false;
        return current_node == other.current_node && current_index == other.current_index;
    }

    // 不等比较
    bool operator!=(const self& other) const {
        return !(*this == other);
    }
};

// B树类定义
template <typename T, int Order>
class b_tree {
    static_assert(Order >= 3, "B树的阶数必须至少为3");

private:
    using node = b_tree_node<T, Order>;
    node* root;          // 根节点
    int node_count;      // 节点数量
    int element_count;   // 元素总数
    const int max_keys;  // 每个节点最多关键字数
    const int min_keys;  // 每个节点最少关键字数

    // 销毁节点
    void destroy_node(node* n) {
        if (!n) return;
        if (!n->is_leaf) {
            for (int i = 0; i <= n->key_count; ++i) {
                destroy_node(n->children[i]);
            }
        }
        delete n;
        node_count--;
    }

    // 分裂子节点
    void split_child(node* parent, int child_idx) {
        node* child = parent->children[child_idx];
        node* new_node = new node();
        new_node->is_leaf = child->is_leaf;
        new_node->key_count = min_keys;

        // 复制关键字
        for (int i = 0; i < min_keys; ++i) {
            new_node->keys[i] = child->keys[i + min_keys + 1];
        }

        // 如果不是叶子节点，复制子节点
        if (!child->is_leaf) {
            for (int i = 0; i < min_keys + 1; ++i) {
                new_node->children[i] = child->children[i + min_keys + 1];
            }
        }

        // 更新子节点的关键字数量
        child->key_count = min_keys;

        // 为新节点在父节点中腾出位置
        for (int i = parent->key_count; i > child_idx; --i) {
            parent->children[i + 1] = parent->children[i];
        }
        parent->children[child_idx + 1] = new_node;

        // 将中间关键字上移到父节点
        for (int i = parent->key_count - 1; i >= child_idx; --i) {
            parent->keys[i + 1] = parent->keys[i];
        }
        parent->keys[child_idx] = child->keys[min_keys];
        parent->key_count++;
        node_count++;
    }

    // 插入非满节点
    void insert_non_full(node* n, const T& key) {
        int i = n->key_count - 1;

        if (n->is_leaf) {
            // 叶子节点，直接插入
            while (i >= 0 && key < n->keys[i]) {
                n->keys[i + 1] = n->keys[i];
                i--;
            }
            n->keys[i + 1] = key;
            n->key_count++;
            element_count++;
        } else {
            // 非叶子节点，找到子节点
            while (i >= 0 && key < n->keys[i]) {
                i--;
            }
            i++;

            // 检查子节点是否满
            if (n->children[i]->key_count == max_keys) {
                // 分裂子节点
                split_child(n, i);
                // 确定插入到哪个子节点
                if (key > n->keys[i]) {
                    i++;
                }
            }
            insert_non_full(n->children[i], key);
        }
    }

    // 查找关键字
    bool search_key(node* n, const T& key) const {
        int i = 0;
        while (i < n->key_count && key > n->keys[i]) {
            i++;
        }

        if (i < n->key_count && key == n->keys[i]) {
            return true;  // 找到关键字
        }

        if (n->is_leaf) {
            return false;  // 叶子节点，未找到
        } else {
            return search_key(n->children[i], key);  // 递归查找子节点
        }
    }

    // 检查B树有效性
    bool is_valid_helper(node* n, int& height, T* min_val, T* max_val) const {
        if (!n) return true;

        // 检查关键字数量是否合法
        if (n == root) {
            if (n->key_count < 1 && node_count > 1) return false;
        } else {
            if (n->key_count < min_keys || n->key_count > max_keys) return false;
        }

        // 检查关键字是否有序
        for (int i = 0; i < n->key_count - 1; ++i) {
            if (n->keys[i] >= n->keys[i + 1]) return false;
        }

        // 检查最小值和最大值约束
        if (min_val && n->keys[0] <= *min_val) return false;
        if (max_val && n->keys[n->key_count - 1] >= *max_val) return false;

        // 叶子节点高度为1
        if (n->is_leaf) {
            height = 1;
            return true;
        }

        // 非叶子节点，检查子节点数量
        if (n->children[0] == nullptr) return false;
        if (n->key_count + 1 != get_child_count(n)) return false;

        // 递归检查子节点
        int child_height = 0;
        T child_min, child_max;

        // 检查第一个子节点
        child_max = n->keys[0];
        if (!is_valid_helper(n->children[0], child_height, min_val, &child_max)) {
            return false;
        }
        height = child_height + 1;

        // 检查中间子节点
        for (int i = 0; i < n->key_count - 1; ++i) {
            int current_height;
            child_min = n->keys[i];
            child_max = n->keys[i + 1];
            
            if (!is_valid_helper(n->children[i + 1], current_height, &child_min, &child_max)) {
                return false;
            }
            if (current_height != child_height) return false;
        }

        // 检查最后一个子节点
        child_min = n->keys[n->key_count - 1];
        if (!is_valid_helper(n->children[n->key_count], child_height, &child_min, max_val)) {
            return false;
        }

        return true;
    }

    // 获取子节点数量
    int get_child_count(node* n) const {
        int count = 0;
        while (count < Order && n->children[count] != nullptr) {
            count++;
        }
        return count;
    }

    // 打印B树
    void print_helper(node* n, int level) const {
        if (!n) return;

        // 打印当前节点
        std::cout << "Level " << level << ": ";
        for (int i = 0; i < n->key_count; ++i) {
            std::cout << n->keys[i] << " ";
        }
        std::cout << "(叶节点: " << (n->is_leaf ? "是" : "否") << ")" << std::endl;

        // 递归打印子节点
        if (!n->is_leaf) {
            for (int i = 0; i <= n->key_count; ++i) {
                print_helper(n->children[i], level + 1);
            }
        }
    }

public:
    // 迭代器类型定义
    using iterator = b_tree_iterator<T, Order>;
    using const_iterator = b_tree_iterator<const T, Order>;

    // 构造函数
    b_tree() : root(nullptr), node_count(0), element_count(0), 
               max_keys(Order - 1), min_keys((Order - 1) / 2) {}

    // 析构函数
    ~b_tree() {
        clear();
    }

    // 插入关键字
    void insert(const T& key) {
        if (search(key)) return;  // 已存在

        if (!root) {
            // 创建根节点
            root = new node();
            root->keys[0] = key;
            root->key_count = 1;
            node_count = 1;
            element_count = 1;
            return;
        }

        // 如果根节点已满，分裂根节点
        if (root->key_count == max_keys) {
            node* new_root = new node();
            new_root->is_leaf = false;
            new_root->children[0] = root;
            node_count++;
            split_child(new_root, 0);
            root = new_root;
        }

        // 插入关键字
        insert_non_full(root, key);
    }

    // 查找关键字
    bool search(const T& key) const {
        if (!root) return false;
        return search_key(root, key);
    }

    // 清空B树
    void clear() {
        if (root) {
            destroy_node(root);
            root = nullptr;
        }
        node_count = 0;
        element_count = 0;
    }

    // 获取元素数量
    int size() const {
        return element_count;
    }

    // 检查B树是否为空
    bool empty() const {
        return element_count == 0;
    }

    // 检查B树有效性
    bool is_valid() const {
        if (!root) return true;
        
        int height;
        return is_valid_helper(root, height, nullptr, nullptr);
    }

    // 打印B树结构
    void print() const {
        if (!root) {
            std::cout << "B树为空" << std::endl;
            return;
        }
        std::cout << "B树结构 (阶数: " << Order << "):" << std::endl;
        print_helper(root, 0);
    }

    // 迭代器相关函数
    iterator begin() {
        return iterator(root);
    }

    iterator end() {
        return iterator();
    }

    const_iterator begin() const {
        return const_iterator(root);
    }

    const_iterator end() const {
        return const_iterator();
    }
};